package tulingxueyuan117;

/**
 * Author: Zhang Dongwei
 * Date: 2022/11/25 13:03
 * 两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。
 *
 * 给你两个整数 x 和 y，计算并返回它们之间的汉明距离。
 */
public class p51_汉明距离_461 {
    public static void main(String[] args) {
        int x = 1577962638, y = 1727613287;
        int res = hammingDistance(x, y);
        System.out.println(res);
    }

//    效果不好
    public static int hammingDistance1(int x, int y) {
//        return countBits(x^y);
        int res = x^y;
        int count = 0;
        String s = Integer.toBinaryString(res);
        System.out.println(s);
        for (int i=0; i<s.length(); i++){
            if (s.charAt(i)=='1'){
                count ++;
            }
        }
        return count;
    }

//    超出限制
    public static int hammingDistance2(int x, int y) {
        return countBits(x^y);
    }
    public static int countBits(int n) {
        int[] res = new int[n+1];
        res[0] = 0;
        for (int i = 1; i <= n; i++){
            if(i%2==0){
                res[i] = res[i/2];
            }else {
                res[i] = res[i-1] + 1;
            }
        }
        return res[n];
    }

    public static int hammingDistance(int x, int y) {
        int res = 0;
        int temp = x^y;
        while (temp!=0){
            temp = temp&(temp-1);
            res ++;
        }
        return res;
    }
}
